package algorithm.stack;

import java.util.Stack;

/**
 * leetcode : https://leetcode.com/problems/evaluate-reverse-polish-notation/
 * 150. Basic Calculator
 * Difficulty : Medium
 *
 * 计算逆波兰表达式
 *
 * Created by yzy on 2019-10-21 16:07
 */
public class EvaluateReversePolishNotation {

    public static void main(String[] args) {
        String[] test1 = new String[]{"2", "1", "+", "3", "*"};
        String[] test2 = new String[]{"4","13","5","/","+"};
        System.out.println(evalRPN(test1));
        System.out.println(evalRPN(test2));
    }


    /**
     * RunTime: 6ms     best than 79.81%
     * Memory:  37.6MB  less than 94.00%
     *
     * 很简单，遇到数字压栈，遇到运算符出栈两个计算后将结果压栈
     * @param tokens
     * @return
     */
    public static int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for(String s : tokens){
            if(s.equals("+")){
                int a = stack.pop();
                int b = stack.pop();
                stack.push(b+a);
            }else if(s.equals("-")){
                int a = stack.pop();
                int b = stack.pop();
                stack.push(b-a);
            }else if(s.equals("*")){
                int a = stack.pop();
                int b = stack.pop();
                stack.push(b*a);
            }else if(s.equals("/")){
                int a = stack.pop();
                int b = stack.pop();
                stack.push(b/a);
            }else{
                stack.push(Integer.valueOf(s));
            }
        }
        return stack.pop();
    }
}
